package com.tys.algorithm.advanced.code.class15;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

// 本题为leetcode原题
// 测试链接：https://leetcode.com/problems/number-of-islands/
// 所有方法都可以直接通过
public class Code02_NumberOfIslands {
    //方法1：感染方法，不用并查集
    public static int numIslands3(char[][] board) {
        int islands = 0;
        //遍历所有的位置
        for (int i = 0; i < board.length; i++) { //遍历行
            for (int j = 0; j < board[0].length; j++) { //遍历列
                if (board[i][j] == '1') { //如果为1
                    islands++; //岛数加1
                    infect(board, i, j); //进行感染过程
                }
            }
        }
        return islands;
    }

    // 从(i,j)这个位置出发，把所有连成一片的'1'字符，变成2
    //递归修改：不能改回去
    public static void infect(char[][] board, int i, int j) {
        //越界或位置值不是1就返回
        if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != '1') {
            return;
        }
        board[i][j] = 2; //为了递归停止
        //感染上
        infect(board, i - 1, j);
        //感染下
        infect(board, i + 1, j);
        //感染左
        infect(board, i, j - 1);
        //感染右
        infect(board, i, j + 1);
    }

    //方法2：使用老的哈希表结构的并查集
    public static int numIslands1(char[][] board) {
        //行大小
        int row = board.length;
        //列大小
        int col = board[0].length;
        //存储每个1的地址：区分出不同的1
        Dot[][] dots = new Dot[row][col];
        //记录产生的Dot多少个
        List<Dot> dotList = new ArrayList<>();
        //初始化并查集
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //遇到1就放入新的地址
                if (board[i][j] == '1') {
                    dots[i][j] = new Dot();
                    dotList.add(dots[i][j]);
                }
            }
        }
        UnionFind1<Dot> uf = new UnionFind1<>(dotList);
        //先将0行和0列位置的处理，方便后面不用判断一些边界条件:不用判断左和上
        //这样处理常数时间最短，写3个for，比写一个for要快
        //遍历所有0行位置
        for (int j = 1; j < col; j++) {
            // (0,j)  (0,0)没有左和上跳过了  (0,1) (0,2) (0,3)
            //左边是1，自己也是1，就合并
            if (board[0][j - 1] == '1' && board[0][j] == '1') {
                //使用dot合并
                uf.union(dots[0][j - 1], dots[0][j]);
            }
        }
        //遍历所有0列位置
        for (int i = 1; i < row; i++) {
            //上面是1，自己是1，就合并
            if (board[i - 1][0] == '1' && board[i][0] == '1') {
                //使用dot合并
                uf.union(dots[i - 1][0], dots[i][0]);
            }
        }
        //遍历剩下的
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (board[i][j] == '1') { //自己是1
                    if (board[i][j - 1] == '1') { //左边是1
                        //合并：自己和左
                        uf.union(dots[i][j - 1], dots[i][j]);
                    }
                    if (board[i - 1][j] == '1') { //上面是1
                        //合并：自己和上
                        uf.union(dots[i - 1][j], dots[i][j]);
                    }
                }
            }
        }
        return uf.sets();
    }

    //只使用地址，啥都不做
    public static class Dot {

    }

    public static class Node<V> {

        V value;

        public Node(V v) {
            value = v;
        }

    }

    public static class UnionFind1<V> {
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parents;
        public HashMap<Node<V>, Integer> sizeMap;

        public UnionFind1(List<V> values) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        //找代表节点
        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        public void union(V a, V b) {
            //a的代表
            Node<V> aHead = findFather(nodes.get(a));
            //b的代表
            Node<V> bHead = findFather(nodes.get(b));
            //属于不同的集合
            if (aHead != bHead) {
                //a集合的大小
                int aSetSize = sizeMap.get(aHead);
                //b集合的大小
                int bSetSize = sizeMap.get(bHead);
                //找大集合
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                //找小集合
                Node<V> small = big == aHead ? bHead : aHead;
                //小挂大
                parents.put(small, big);
                //更新数量
                sizeMap.put(big, aSetSize + bSetSize);
                //移除小的计数
                sizeMap.remove(small);
            }
        }

        //返回个数
        public int sets() {
            return sizeMap.size();
        }

    }

    //方法3：数组结构的并查集，相比哈希表优化常数时间
    public static int numIslands2(char[][] board) {
        //列
        int row = board.length;
        int col = board[0].length;
        UnionFind2 uf = new UnionFind2(board);
        for (int j = 1; j < col; j++) {
            if (board[0][j - 1] == '1' && board[0][j] == '1') {
                uf.union(0, j - 1, 0, j);
            }
        }
        for (int i = 1; i < row; i++) {
            if (board[i - 1][0] == '1' && board[i][0] == '1') {
                uf.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (board[i][j] == '1') {
                    if (board[i][j - 1] == '1') {
                        uf.union(i, j - 1, i, j);
                    }
                    if (board[i - 1][j] == '1') {
                        uf.union(i - 1, j, i, j);
                    }
                }
            }
        }
        return uf.sets();
    }

    public static class UnionFind2 {
        private int[] parent;
        private int[] size;
        private int[] help;
        private int col; //列号
        private int sets; //集合大小

        public UnionFind2(char[][] board) {
            //列数
            col = board[0].length;
            sets = 0;
            //行数
            int row = board.length;
            //行*列是总长度：假设没有查过整数最大值
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
            for (int r = 0; r < row; r++) {
                for (int c = 0; c < col; c++) {
                    if (board[r][c] == '1') {
                        int i = index(r, c);
                        parent[i] = i;
                        size[i] = 1;
                        sets++;
                    }
                }
            }
        }

        //计算下标位置：i
        // (r,c) -> i
        private int index(int r, int c) {
            //行*总列数+列
            return r * col + c;
        }

        // 原始位置 -> 下标
        //根据 i 找
        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        //合并
        public void union(int r1, int c1, int r2, int c2) {
            //找到索引1
            int i1 = index(r1, c1);
            //找到索引2
            int i2 = index(r2, c2);
            //找到索引1的父
            int f1 = find(i1);
            //找到索引2的父
            int f2 = find(i2);
            //不是一个
            if (f1 != f2) {
                //f1大于f2
                if (size[f1] >= size[f2]) {
                    //f1大小累加f2大小
                    size[f1] += size[f2];
                    //f1挂f2，f1为f2父
                    parent[f2] = f1;
                } else {
                    //f2累加f1
                    size[f2] += size[f1];
                    //f2为f1父
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        //返回数量
        public int sets() {
            return sets;
        }

    }

    // 为了测试
    public static char[][] generateRandomMatrix(int row, int col) {
        char[][] board = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                board[i][j] = Math.random() < 0.5 ? '1' : '0';
            }
        }
        return board;
    }

    // 为了测试
    public static char[][] copy(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        char[][] ans = new char[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                ans[i][j] = board[i][j];
            }
        }
        return ans;
    }

    // 为了测试
    public static void main(String[] args) {
        int row = 0;
        int col = 0;
        char[][] board1 = null;
        char[][] board2 = null;
        char[][] board3 = null;
        long start = 0;
        long end = 0;

        row = 1000;
        col = 1000;
        board1 = generateRandomMatrix(row, col);
        board2 = copy(board1);
        board3 = copy(board1);

        System.out.println("感染方法、并查集(map实现)、并查集(数组实现)的运行结果和运行时间");
        System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);

        start = System.currentTimeMillis();
        System.out.println("感染方法的运行结果: " + numIslands3(board1));
        end = System.currentTimeMillis();
        System.out.println("感染方法的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(map实现)的运行结果: " + numIslands1(board2));
        end = System.currentTimeMillis();
        System.out.println("并查集(map实现)的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
        end = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");

        System.out.println();

        row = 10000;
        col = 10000;
        board1 = generateRandomMatrix(row, col);
        board3 = copy(board1);
        System.out.println("感染方法、并查集(数组实现)的运行结果和运行时间");
        System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);

        start = System.currentTimeMillis();
        System.out.println("感染方法的运行结果: " + numIslands3(board1));
        end = System.currentTimeMillis();
        System.out.println("感染方法的运行时间: " + (end - start) + " ms");

        start = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
        end = System.currentTimeMillis();
        System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");

    }

}
